package com.zhugang.week11;

/**
 * @program algorithms
 * @description: coinChange2
 * @author: chanzhugang
 * @create: 2022/09/01 22:06
 */
public class CoinChange2 {

    /**
     * 322 零钱兑换
     *
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange2(int[] coins, int amount) {
        // 抽象为爬楼梯模型: 每次爬1、2、5个台阶，做少需要多少步
        // dp[i]:表示凑够i元最少需要多少个硬币，  一维数组
        // dp[i] = min(dp[i - 1], dp[i - 2], dp[i - 5]) + 1
        int[] dp = new int[amount + 1];
        for (int i = 0; i <= amount; i++) {
            // 求最小值时一般都要初始化为最大值
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;

        int k = coins.length;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < k; j++) {
                if (i - coins[j] >= 0 && dp[i - coins[j]] != Integer.MAX_VALUE) {
                    // 取最小值
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }

                /*if (i - coins[j] >= 0 && dp[i - coins[j]] != Integer.MAX_VALUE && dp[i - coins[j]] + 1 < dp[i]) {
                    // 更新最小值
                    dp[i] = dp[i - coins[j]] + 1;
                }*/
            }
        }
        if (dp[amount] == Integer.MAX_VALUE) {
            return -1;
        }
        return dp[amount];
    }
}